def solveNQueens(n: int):
    def recure(board):
        row = len(board)
        if row == n:
            res.append(list(board))
            return
        for col in range(n):
            if not is_valid(board, row, col):
                continue
            board.append('.' * col + 'Q' + '.' * (n - col - 1))
            recure(board)
            board.pop()

    def is_valid(board, row, col):
        if row == 0:
            return True
        # 判断列是否有冲突：
        for i in board:
            if i[col] == 'Q':
                return False
        # 检查右上是否冲突：(注意边界)
        if col < n - 1:
            for i, j in zip(range(row - 1, -1, -1), range(col + 1, n, 1)):
                if board[i][j] == 'Q':
                    return False
        # 检查左上是否有冲突：
        if col > 0:
            for i, j in zip(range(row - 1, -1, -1), range(col - 1, -1, -1)):
                if board[i][j] == 'Q':
                    return False
        return True

    res = []
    board = []
    recure(board)
    return res

if __name__ == '__main__':
    n = input('please input the size of board:')
    res = solveNQueens(int(n))
    for board in res:
        for row in board:
            print(' '.join(row), end='')
            print('')

        print('*' * 20)
    print(len(res))